package need_learn.coding.didi;

import java.util.HashSet;
import java.util.Set;
/**
 * TODO 滴滴， 字符串操作，最长子串、最长回文子串
 *
 * @author david
 * @version 1.0
 * @date 2021/4/20 14:56
 */
public class ZuiChangZiChuan {
    //1. 求一个字符串的最长不重复子串 abcgahf - bcgahf   学习链接：https://blog.csdn.net/weixin_39990138/article/details/114203353
    //2. 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。O(1) 额外空间
    //   不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    public static void main(String[] args) {
        String s = "hnwnkuewhsqmgbbuqcljjivswmdkqtbxixmvtrrbljptnsnfwzqfjmafadrrwsofsbcnuvqhffbsaqxwpqcac";
        //滑动窗口找最长子串
        System.out.println(lengthOfLongestSubstring(s));
        //暴力查找最长子串
        System.out.println(lengthOfLongestSubstring2(s));

        //暴力查找最长回文子串
        System.out.println(longestPalindrome(s));
        //中心拓展法
        System.out.println(longestPalindrome2(s));
    }

    /**
     * 滑动窗口思想：如果确定子串s[i,j](假设表示字符串的第i个字符到第j-1个字符表示的子串)，那么只需要比较s[j]是否与子串s[i,j]重复即可
     * 若重复：记录此时滑动窗口大小，并与最大滑动窗口比较，赋值。然后滑动窗口大小重定义为1，头位置右移一个单位。
     * 若不重复：滑动窗口头不变，结尾+1，整个窗口加大1个单位。继续比较下一个
     */
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Object> set = new HashSet<>();
        int ans = 0, i = 0, j = 0;
        while (i < n && j < n) {
            //如果没有字串字符没有重复，追加比较字串长度
            if (!set.contains(s.charAt(j))) {
                set.add(s.charAt(j++));
                ans = Math.max(ans, j - i);
            } else {
                //如果字串字符出现重复，重置子串初始字符
                set.remove(s.charAt(i++));
            }
        }
        return ans;
    }

    //暴力迭代
    public static int lengthOfLongestSubstring2(String s) {
        int start, end;
        String count = "";
        String str;
        for (start = 0; start <= s.length(); start++) {
            for (end = start + 1; end <= s.length(); end++) {
                //获取字符串
                str = s.substring(start, end);
                //如果遍历到最长的原串
                if (end == s.length()) {//对比长度 如果发现更长的就覆盖赋值
                    if (count.length() < str.length()) {//对比长度
                        count = str;
                    }
                    break;
                } else {
                    //比较结尾字符是否与起始字符相等
                    if (str.contains(s.substring(end, end + 1))) {//当有重复时候，处理，跳出循环让start++
                        if (count.length() < str.length()) {//对比长度 如果发现更长的就覆盖赋值
                            count = str;
                        }
                        break;
                    }
                }
            }

        }
        return count.length();
    }



    //暴力破解法
    public static String longestPalindrome(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String tmp = s.substring(i, j);
                if (isPalindromic(tmp) && tmp.length() > max) {
                    ans = tmp;
                    max = j - i;
                }
            }
        }
        return ans;
    }

    private static boolean isPalindromic(String s) {
        System.out.println();
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    //中心拓展法
    public static String longestPalindrome2(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i+1);

            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len-1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    public static  int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return (R-1) - (L+1) + 1;
    }
}